今天的題單：

• Invert Binary Tree

• Valid Anagram

• Binary Search

226. Invert Binary Tree

思路：從最底層的節點開始把左右子樹的 pointer 交換，一層一層往上，最後翻轉 root 的兩顆子樹。
用 post-order traversal 可以達成（先訪子節點再訪父節點）。以前學 tree traversal 的時候是用遞迴實作，這題我練習用迴圈方式寫。實作參考了這篇文章。需要用 stack 來存 node。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // Post-order traversal, iterative
    TreeNode* invertTree(TreeNode* root) {

        if (root == nullptr) return root;

        TreeNode* p = root;

        stack<pair<TreeNode*, int>> stk;
        stk.push({root, 0});

        while (!stk.empty()) {
            // peek the top node
            TreeNode* node = stk.top().first;
            int visited = stk.top().second;

            stk.pop();

            if (!visited) {
                // if node is leaf
                if (node->left == nullptr && node->right == nullptr)
                    stk.push({node, 1});

                // if node is not leaf
                stk.push({node, 1});
                if (node->right != nullptr)
                    stk.push({node->right, 0});
                if (node->left != nullptr)
                    stk.push({node->left, 0});

            } else {
                // swap the left and right child
                swap(node->right, node->left);
            }
        }
        
        return root;
    }
};

// O(n) time and space complexity

242. Valid Anagram

思路：統計不同字母的個數，比較數量

• 只考慮 english letter (a-z) 的話用 hash table

• Follow up 考慮到 unicode 用 map

class Solution {
public:
    // Using hashtable
    bool isAnagram(string s, string t) {
        vector<int> hashtbl_S(26, 0);
        vector<int> hashtbl_T(26, 0);

        for(int i=0; i<s.length(); i++) {
            hashtbl_S[s[i] % 26]++;
        }

        for(int i=0; i<t.length(); i++) {
            hashtbl_T[t[i] % 26]++;
        }

        for (int i=0; i<26; i++) {
            if (hashtbl_S[i] != hashtbl_T[i])
                return false;
        }

        return true;


    }
};

class Solution {
public:
    // Using map
    bool isAnagram(string s, string t) {
        map<char, int> s_map;
        map<char, int> t_map;

        for (int i=0; i<s.length(); i++){
            if (s_map.find(s[i]) != s_map.end())
                s_map[s[i]]++;
            else
                s_map[s[i]] = 1;
        }

        for (int i=0; i<t.length(); i++){
            if (t_map.find(t[i]) != t_map.end())
                t_map[t[i]]++;
            else
                t_map[t[i]] = 1;
        }

        for (map<char, int>::iterator it=s_map.begin(); it!=s_map.end(); it++) {
            if (t_map.find(it->first) == t_map.end())   // char not found in t
                return false;
            if (s_map[it->first] != t_map[it->first])   // num of char does not match
                return false;
        }

        if (s_map.size() != t_map.size())
            return false;
        else
            return true;
        
    }
};

704. Binary Search

實作經典的 binary search。根據猜測值與 target 的比較大小縮小左右區間。
邊界需要特別注意，這篇文章有詳細解說。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid -1;
            } else {
                return mid;
            }
        }
        return -1;
    }
};